

function say() {
    alert("116. 填充每个节点的下一个右侧节点指针");
}
say();


/**
 * @param {Node} root
 * @return {Node}
 */
var connect = function(root) {
    // 层序遍历 存储节点node  2:50-3:05

    if(!root){
        return null
    }

    var levelArr = []
    var rootArr = [root, null]
    var resArr = []
    while(rootArr.length){
        var first = rootArr.shift()
        if(first){
            levelArr.push(first)
            if(first.left) {
                rootArr.push(first.left)
            }
            if(first.right) {
                rootArr.push(first.right)
            }
        }else {
            resArr.push(levelArr)
            levelArr = []
            if(rootArr.length) {
                rootArr.push(null)
            }
        }
    }

    for(var i = 0; i < resArr.length; i++){
        var itemArr = resArr[i]
        for(var j = 0; j < itemArr.length; j++){
            var current = itemArr[j]
            if(j + 1 < itemArr.length){
                var nextNode = itemArr[j + 1]
                current.next = nextNode
            }
        }
    }
    return root
};
